#include <iostream>
#include <cstdlib>

typedef struct TreeNode{
    int data;
    struct TreeNode *left, *right;
}TreeNode;

TreeNode *CreateNode(int data) {
    auto *node = new TreeNode;
    node->data = data;
    node->right = nullptr;
    node->left = nullptr;

    return node;
}

TreeNode *InsertTree(TreeNode* root, int data) {
    if (root == nullptr) {
        return CreateNode(data);
    }
    if (data < root->data) {
        root -> left = InsertTree(root -> left, data);
    } else {
        root -> right = InsertTree(root -> right, data);
    }
    return root;
}

void FreeNode(TreeNode* root) {
    if (root != nullptr) {
        FreeNode(root ->left);
        FreeNode(root -> right);
        free(root);
    }
}
void PreOrder(TreeNode * root) {
    if (root != nullptr) {
        printf("%d ", root -> data);
        PreOrder(root->left);
        PreOrder(root -> right);
    }
}

void InOrder(TreeNode * root) {
    if (root != nullptr) {
        InOrder(root->left);
        printf("%d ", root -> data);
        InOrder(root -> right);
    }
}

void PostOrder(TreeNode * root) {
    if (root != nullptr) {
        PostOrder(root->left);
        PostOrder(root -> right);
        printf("%d ", root -> data);
    }
}


int main() {
    TreeNode *tree = nullptr;
    tree = InsertTree(tree, 14);
    InsertTree(tree, 7);
    InsertTree(tree, 20);
    InsertTree(tree, 4);
    PreOrder(tree);
    printf("\n");
    PostOrder(tree);
    printf("\n");
    InOrder(tree);
    return 0;
}
